//
// Created by LiuYou on 2021/11/29.
//

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>


/*
 * 此版本为最终的版本。
 */
static void selectionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // todo 笔记: 外层循环的的条件 - 1 和 不 -1 最后的结果是一样的。
    //  区别: - 1 的话, 就是例如: arr 的长度为 5。那么就是 arr[3]位置的值排好序后, 此时就只剩下了 arr[4]位置的值了。
    //  而 arr[4]位置的值一定是最大的。
    //  而不减1的话, 即 arr[4]为最后一个位置也选择排序一下, 此时进入内层循环, j = 5, j < arr.size() 是不成立的。
    //  因为 数组的大小就是 5。然后会进行一步 swap();操作, 但是此时的这个 swap();是 std::swap(arr[4], arr[4]);
    //  即自己交换自己, 其实没有必要执行的。
    //  综上, 还是加上 - 1, 这样就不要做一次无用的 for循环判断和 swap();函数调用了。
    for (int i = 0; i < arr.size() - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); ++j) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            } else {
            }
        }
        std::swap( arr[minIndex], arr[i] );
    }
}


#ifdef version3

/*
 * 运行成功。但是我想再考虑一下 for 循环结束的条件 -> 即边界。
 */
static void selectionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = 0; i < arr.size() /*- 1*/; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size() /*- 2*/; ++j) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        std::swap( arr[minIndex], arr[i] );
    }
}

#endif


#ifdef version1

/*
 * 可以运行, 但是结果是不正确的。
 */
static void selectionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = 0; i < arr.size() - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size() - 2; ++j) {
            if (arr[minIndex] > arr[j]) {
                std::swap( arr[minIndex], arr[j] );
            }
        }
    }
}

#endif


int main(int argc, char** argv) {
    std::vector<int> arr{3, 2, 5, 4, 1};
    std::vector<int> arr2( arr );

    {
        selectionSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::sort( arr2.begin(), arr2.end());
        std::copy( arr2.begin(), arr2.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}
